class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int sizeOfNums = nums.size();
        int halfSize = sizeOfNums / 2;
        /*
        哈希查找：时间复杂度O(n),空间复杂度O(n)
        */
        unordered_map<int,int> um;
        for(int num : nums){
            if(++um[num] > halfSize)  return num;
        }
        return NULL;
    }
};

/*************************************************/
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        /*
        排序后查找：时间复杂度（使用STL的sort()），空间复杂度O(1)
        */
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

/***************************************************/
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        /*
        基于Partition函数的排序：时间复杂度O(n)，空间复杂度O(1);
        根据题目条件，我们需要找到数组的中位数；
        每次选中的数据排序后左边均是小于它的数，右边都是大于它的数，若是它的下标刚好是n/2,则说明它就是数组的中位数；
        若是它的下标小于n/2，则说明中位数位于它的右端，我们可以从它左边的数组内继续寻找；若是下标大于n/2同理；
        上述过程是一个典型的递归过程.
        */
        int sizeOfNums = nums.size();
        int begin = 0;
        int end = sizeOfNums - 1;
        int medium = partition(nums, begin, end);
        while(medium != sizeOfNums / 2){
            if(medium < sizeOfNums / 2){
                begin = medium + 1;
                medium = partition(nums, begin, end);
            }else{
                end = medium - 1;
                medium = partition(nums, begin, end);
            }
        }

        int result = nums[medium];
        if(!checkMoreThanHalf(nums, sizeOfNums, result))  result = 0;

        return result;
    }

    //随机数快速排序
    int partition(vector<int>& nums, int begin, int end){
        if(begin > end)  return begin;
        int index = RandomInRange(begin, end);
        if(index != end)  swap(nums[index], nums[end]);
        int small = begin - 1;//指向小于或等于参考值的最左侧

        for(index = begin; index < end; ++index){
            if(nums[index] < nums[end]){
                ++small;
                if(small != index)  swap(nums[small], nums[index]);
            }
        }

        if(++small != end)  swap(nums[small], nums[end]);
        return small;
    }

    //利用系统时间作为种子，产生[begin, end]之间的随机整数，但对于有大量重复元素的数组排序太慢
    int RandomInRange(int begin, int end){
        srand((unsigned)time(NULL));
        return (rand() % (end - begin + 1)) + begin;
    }

    //检查结果是否真的是出现频率超过数组一半
    bool checkMoreThanHalf(vector<int>& nums, int length, int result){
        int times = 0;
        for(int i = 0; i < length; ++i){
            if(nums[i] == result)  ++times;
        }

        if(times * 2 <= length)  return false;
        return true;
    }
};

/*********************************************************************************************/
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        /*
        根据数组特点，时间复杂度O(n)的算法：
        一个数出现次数超过一半，意味着它比数组中其他数字加起来出现的次数都要多；
        我们可以保存两个数字，一个是当前数字，一个是它出现的的次数，每一碰到下一个数与当前数字相同，则次数+1，反之则-1；
        当次数减至0时，则我们开始保存下一个数字。那么出现最多的数字则是最后一个把次数设为1的数字。
        */
        int sizeOfNums = nums.size();
        if(sizeOfNums < 1)  return 0;

        int result = nums[0];
        int times = 1;
        for(int i = 1; i < sizeOfNums; ++i){
            if(nums[i] != result){
                --times;
                if(times == 0)  result = nums[i];
                else  continue;
            }
            ++times;
        }
        if(!checkMoreThanHalf(nums, sizeOfNums, result))  result = 0;
        return result;
    }

    //检查结果是否真的是出现频率超过数组一半
    bool checkMoreThanHalf(vector<int>& nums, int length, int result){
        int times = 0;
        for(int i = 0; i < length; ++i){
            if(nums[i] == result)  ++times;
        }

        if(times * 2 <= length)  return false;
        return true;
    }
};